/*
题目: 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

https://leetcode.cn/problems/merge-intervalsH
 */
public class Merge {
    public int[][] merge(int[][] intervals) {
        List<int[]> list = new ArrayList<> ();

        Arrays.sort(intervals, new Comparator<int[]> () {
            public int compare(int[] o1, int[] o2) {
                if (o1[0] != o2[0]) {
                    return o1[0] - o2[0];
                }
                return o1[1] - o2[1];
            }
        });

        int i = 0;
        while (i < intervals.length) {
            int[] elem = intervals[i++];
            int start = elem[0], end = elem[1];
            while (i < intervals.length && end >= intervals[i][0]) {
                end = Math.max(intervals[i++][1], end);
            }
            list.add(new int[] {start, end});
        }

        int[][] src = new int[list.size()][2];
        for (int pos = 0; pos < list.size(); pos++) {
            src[pos] = list.get(pos);
        }
        return src;
    }
}
